package com.leetcode.algorithm.y22.m07.w4;

/**
 * 707. 设计链表
 * 
 * https://leetcode.cn/problems/design-linked-list/
 * 
 * @author jie.deng
 *
 */
public class MyLinkedList01 {

	private SinglyListNode sentinel;
	private int cnt;

	public MyLinkedList01() {
		sentinel = new SinglyListNode(0, null);
	}

	public int get(int index) {
		if (index < 0 || index >= this.cnt) {
			return -1;
		}
		SinglyListNode node = getNodeAtIndex(index);
		return node.val;
	}

	/**
	 * 根据索引查找节点
	 * 
	 * @param index [0,cnt-1]
	 * @return
	 */
	private SinglyListNode getNodeAtIndex(int index) {
		assert index >= 0 && index < this.cnt;
		SinglyListNode cur = sentinel;
		while (index >= 0) {
			cur = cur.next;
			index--;
		}
		return cur;
	}

	/**
	 * 查找前一个节点
	 * 
	 * @param index [0,cnt]
	 * @return
	 */
	private SinglyListNode getPrevNode(int index) {
		assert index >= 0 && index <= this.cnt;
		if (index == 0) {
			return sentinel;
		}
		return getNodeAtIndex(index - 1);
	}

	public void addAtHead(int val) {
		addAtIndex(0, val);
	}

	public void addAtTail(int val) {
		addAtIndex(this.cnt, val);
	}

	public void addAtIndex(int index, int val) {
		if (index > this.cnt) {
			return;
		}
		if (index <= 0) {
			index = 0;
		}

		SinglyListNode cur = getPrevNode(index);
		SinglyListNode node = new SinglyListNode(val, cur.next);
		cur.next = node;
		this.cnt++;
	}

	public void deleteAtIndex(int index) {
		if (index < 0 || index >= this.cnt) {
			return;
		}
		SinglyListNode cur = getPrevNode(index);
		cur.next = cur.next.next;
		this.cnt--;
	}

	private static class SinglyListNode {
		int val;
		SinglyListNode next;

		SinglyListNode(int val, SinglyListNode next) {
			this.val = val;
			this.next = next;
		}
	}
}